package com.yulongtian.weekCompetition.month202302.week04;

import java.util.Arrays;

/**
 * 部分通过
 * 45 / 63 个通过测试用例
 *
 * @author yulongTian
 * @create 2023-02-26 11:19
 */
public class Test03 {
    public static void main(String[] args) {
        System.out.println(new Test03().maxNumOfMarkedIndices(new int[]{42, 83, 48, 10, 24, 55, 9, 100, 10, 17, 17, 99, 51, 32, 16, 98, 99, 31, 28, 68, 71, 14, 64, 29, 15, 40}));
    }

    /**
     * 双指针方法
     *
     * @param nums
     * @return
     */
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        if (nums[0] * 2 > nums[n - 1] || n == 1) {
            return 0;
        }
        int i = 0;
        for (int j = (n + 1) / 2; j < n; j++) {
            if (nums[i] * 2 <= nums[j]) {
                i++;
            }
        }
        return i * 2;
    }

//    /**
//     * 二分方法
//     * 排序后，i<j
//     * 如果想要尽可能多的匹配，那么数组中最小的数一定要参与匹配
//     * 如果不参与匹配，那么可以把其它的数字换成最小的数，同样可以匹配
//     * 或者
//     * 数字越大，越可以作为j
//     * 数字越小，越可以作为i
//     * <p>
//     * 排序后，选择最小的k个数去和最大的k个数匹配
//     * k的范围   [0,n/2+1)
//     *
//     * @param nums
//     * @return
//     */
//    public int maxNumOfMarkedIndices(int[] nums) {
//        Arrays.sort(nums);
//        int n = nums.length;
//        //开区间  二分
//        int left = 0;
//        int right = n / 2 + 1;
//        while (left + 1 < right) {
//            int k = (left + right) / 2;
//            boolean flag = true;
//            for (int i = 0; i < k; i++) {
//                if (nums[i] * 2 > nums[(n + i - k) % n]) {
//                    flag = false;
//                    break;
//                }
//            }
//            if (flag) {
//                //如果成立
//                left = k;
//            } else {
//                right = k;
//            }
//        }
//        return left * 2;
//    }

    //    45 / 63 个通过测试用例
//    public int maxNumOfMarkedIndices(int[] nums) {
//        //排序
//        Arrays.sort(nums);
//        int len = nums.length;
//        int min = nums[0];
//        if (min * 2 > nums[len - 1]) {
//            return 0;
//        }
//        double[] binary = new double[len];
//        for (int i = 0; i < nums.length; i++) {
//            binary[i] = nums[i] * 1.0 / 2;
//        }
//        int num_index = len - 1;
//        int binary_index = len - 1;
//        int ans = 0;
//        boolean[] is_used = new boolean[len];
//        while (num_index >= 0 && binary_index >= 0) {
//            if (is_used[binary_index]) {
//                binary_index--;
//                continue;
//            }
//            if (nums[num_index] <= binary[binary_index]) {
//                ans++;
//                is_used[num_index] = true;
//                is_used[binary_index] = true;
//                num_index--;
//                binary_index--;
//            } else {
//                num_index--;
//            }
//        }
//        return ans * 2;
//    }

}
